package train.DAT621;

import java.util.Arrays;

public class LeetCode621 {
    public static void main(String[] args) {
//        int[] a={2,6,0,4,5,9};
//        int[] ints = insertSort(a);
//        for (int anInt : ints) {
//            System.out.println("anInt = " + anInt);
//        }

//        String[] a={"abcd","abcde","abcef","a"};
//        String s = pubZ(a);
//        System.out.println(s);

//        String s1="abcd";
//        String s2="dcba";
//        System.out.println(arraySign(s1, s2));
//        int[] a= {1,5,-2,-4,0};
//        System.out.println(conDup(a));
        System.out.println(addBir("100", "110010"));
    }

    //合并已排序数组
    public static int[] mergeNums(int[] nums1,int[] nums2){
        int[] a=new int[nums1.length+ nums2.length];
        int i=0,j=0,k=0;
        while(i< nums1.length&&j< nums2.length){
            if(nums1[i]>nums2[j]) {
                a[k]=nums2[j];
                k++;
                j++;
            } else{
                a[k]=nums1[i];
                i++;
                k++;
            }
        }
        while(j<nums2.length){
            a[k]=nums2[j];
            j++;
            k++;
        }
        while(i< nums1.length){
            a[k]=nums1[i];
            i++;k++;
        }
         return a;
    }

    //公共前缀
    public static String pubZ(String[] nums){
        String s=null;
        if(nums[0].length()>nums[1].length())
            s=nums[1];
        else s=nums[0];
        for (int i = 0; i < nums.length; i++) {
            while(!nums[i].startsWith(s)&&s.length()!=0)
                s=s.substring(0,s.length()-1);
        }
      return s;
    }

    //仅执行一次字符串交换能否使两个字符串相等
    public static boolean arraySign(String s1,String s2){
       int temp=2;
       int i=0,j=0;
       boolean k=true;

          for (int l = 0; l < s1.length(); l++) {
              if(s1.charAt(l)!=s2.charAt(l)) {
                  temp--;
                  if(temp==1)
                  {
                      i=l;
                  }else if(temp==0)
                      j=l;
                  else
                  {
                      return false;
                  }
              }
      }
          if(s1.charAt(i)!=s2.charAt(j)||s1.charAt(j)!=s2.charAt(i))
              return false;
        return true;
    }

    //插入排序
    public static int[] insertSort(int[] nums){
        int temp=0;
        for (int i = 1; i < nums.length; i++) {
            for (int j = i; j >0; j--) {
                if(nums[j]<nums[j-1])
                {
                    temp=nums[j];
                    nums[j]=nums[j-1];
                    nums[j-1]=temp;
                }

            }
        }
        return nums;
    }

    //选择排序
    public static int[] choiceSort(int[] nums){
        int min=0,temp=0,i=0,j=0,index=0;
        boolean c=false;
        for ( i = 0; i < nums.length-1; i++) {
            min=nums[i];
            for ( j = i; j < nums.length ; j++) {
                if(nums[j]<min) {
                    min=nums[j];
                    index=j;
                    c=true;
                }
            }
            temp=nums[i];
            nums[i]=min;
            if(c)
              nums[index]=temp;
            c=false;
        }
        return nums;
    }

    //快乐数--有问题
    public static boolean isHappy(int n){
        int sum=0;
        int temp=n;
        int k=0;
        while(temp!=1){
            k=n%10;
            if(k!=0)
            sum+=k*k;
            n=n/10;
            temp=n;
            if(sum==4) return false;
        }


        return true;
    }

    //只出现一次的数字
    public static int singleNumber(int[] nums){
        int temp;
        for (int i = nums.length-1; i >0; i--) {
            for (int j = 0; j < i; j++) {
                if(nums[j]>nums[j+1])
                {
                    temp=nums[j];
                    nums[j]=nums[j+1];
                    nums[j+1]=temp;
                }
            }
        }
        if(nums.length==1){
            return nums[0];
        } else{
            for (int i = 0; i < nums.length-2; i=i+2) {
                if(nums[i]!=nums[i+1])
                    return nums[i];
            }

            if(nums[nums.length-1]!=nums[nums.length-2])
                return nums[nums.length-1];
        }


        return 0;
    }

    //多数元素
    public static int majElement(int[] nums){
        int min=0,temp=0;
        for (int i = 0; i < nums.length-1; i++) {
            min=nums[i];
            for (int j = i; j < nums.length ; j++) {
                if(nums[i]>nums[j])
                {
                    temp=nums[i];
                    nums[i]=nums[j];
                    nums[j]=temp;
                }
            }

        }
        int max=nums[nums.length-1];
        int[] a=new int[max];
        int dep=nums.length/2;
        int num=0;
        for (int i = 0; i < nums.length-1; i++) {
            if(nums[i]==nums[i+1]) num++;
            else {
                if(num+1>dep)
                    return nums[i];
                else num=0;
            }
            if(i==nums.length-2)
                if(num+1>dep)
                    return nums[i];
        }

        return nums[0];
    }

    //存在重复元素
    public static boolean conDup(int[] nums){
        int temp=0;
        int dp=0;
        int c=0;
        for (int i = 1; i < nums.length; i++) {
            for (int j = i; j >=1 ; j--) {
                if(nums[j]<nums[j-1]){
                    temp=nums[j];
                    nums[j]=nums[j-1];
                    nums[j-1]=temp;
                }
            }
        }
        for (int i = 0; i < nums.length-1; i++) {
            if(nums[i]==nums[i+1]) return true;
        }
        return false;
    }

    //二进制求和
    public static String addBir(String a,String b){
        int sum=0;
        int dep=0;
        int i1=0;
        int c=0;
        String s=null;
        int i=a.length()>b.length()?a.length():b.length();
        sum=i;
        int j=a.length()<b.length()?a.length():b.length();
        int[] k=new int[i+1];
        for ( i1 = 0; i1 <j; i1++) {
            c=(a.charAt(a.length()-1-i1)-48)+(b.charAt(b.length()-1-i1)-48)+dep;
                if(c==2){
                    k[i]=0;
                    i--;
                    dep=1;
                }else if(c==3){
                    k[i]=1;
                    i--;
                    dep=1;
                }
                else
                {
                    k[i]=c;
                    i--;
                    dep=0;
                }
            }

        if(a.length()>b.length()) s=a;
        else s=b;
        for (int l = sum-j-1; l >=0 ; l--) {
            if(dep+(s.charAt(l)-48)==2){
                k[i]=0;
                i--;
                dep=1;
            }else{
                if(dep+(s.charAt(l)-48)==1)
                {
                    k[i]=1;
                    i--;
                    dep=0;
                }else{
                    k[i]=s.charAt(l)-48;
                    i--;dep=0;
                }

            }

        }
        if(dep==1){
            k[0]=1;
        }
        StringBuffer buffer = new StringBuffer();
        if(a.length()==1&&b.length()==1 && a.charAt(0)=='0'&&b.charAt(0)=='0')
            return "0";
        for (int l = 0; l <k.length; l++) {
            if(l==0&&k[0]==0) continue;

            buffer.append(k[l]);
        }
        return buffer.toString();
    }

}
